﻿// Allowance POJ - 3040.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>
#include <map>


using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-3040
/*
作为创纪录的牛奶产量的奖励，约翰决定每周给贝西一小笔零用钱。FJ拥有一组N（1 <= N <= 20）种不同面额的硬币，
其中每个面额的硬币均可整除较大面额的硬币（例如，1分硬币、5分硬币、10分硬币和50分硬币）。
使用给定的硬币面额，他想每周至少支付给贝西一定金额C（1 <= C <= 100,000,000）。
请帮助他计算他最多可以支付贝西多少周。

输入

第1行：两个以空格分隔的整数：N和C
第2行到第N+1行：每行对应一个硬币面额，并包含两个整数：
硬币面额V（1 <= V <= 100,000,000）和约翰手中该面额的硬币数量B（1 <= B <= 1,000,000）。
输出

第1行：一个整数，表示约翰可以支付贝西至少C零用钱的周数。

3 12
5 4
2 1
1 2


3 6
10 1
1 100
5 120

111

3 6
10 3
20 4
40 5

12

3 51
100 1
50 4
1 2

4


3 51
1 2
50 4
100 1

4

20 100000000
67108864 1000000
33554432 1000000
16777216 1000000
8388608 1000000
4194304 1000000
2097152 1000000
1048576 1000000
524288 1000000
262144 1000000
131072 1000000
65536 1000000
32768 1000000
16384 1000000
8192 1000000
4096 1000000
2048 1000000
1024 1000000
512 1000000
256 1000000
128 1000000

1340054


输入详情：
FJ每周想支付给贝西6美分。他手上有100个1美分硬币，120个5美分硬币和1个10美分硬币。

输出详情：
FJ可以用一个10美分硬币多支付给贝西1周，然后用两个5美分硬币支付给贝西10周，
最后用一个1美分硬币和一个5美分硬币支付给贝西100周。

*/

int n, c;
int ans;
map<int, int> mm;
map<int, int> usedmm;
int limit;

void GetusedArr() {
	
	for (map<int, int>::reverse_iterator it = mm.rbegin(); it != mm.rend(); it++) {
		if (it->second != 0 && limit >0  && limit >= it->first) {
			int used = min(limit / it->first, it->second);
			limit -= used * it->first;
			usedmm[it->first] += used;
		}

		if (limit == 0) break;
	}

	//贪心完所有金币 还没超出需要的金额 使用最小的进行填充
	if (limit > 0) {
		for (map<int, int>::iterator it = mm.begin(); it != mm.end(); it++) {
			if (it->second > 0 && limit > 0 && mm[it->first] > usedmm[it->first]) {
				int used = 1;  int v = it->first; int cnt = it->second;
				limit -= v;
				usedmm[v] += 1;
			}
		}
	}

	return;
}

void solve() {

	while (1) {
		usedmm.clear();
		limit = c;
		GetusedArr();

		if (limit > 0) {
			cout << ans << endl; return;
		}
		//按照usedmm  查看能取几次
		int minget = 1000010;
		for (map<int, int>::iterator it = usedmm.begin(); it != usedmm.end(); it++) {
			int v = it->first;
			minget = min(minget, mm[v]/it->second);
			/*if (minget == 0) {
				cout << "v= " << v << " ,cnt = " << mm[v] << " .used v= " << it->first << " .used cnt = " << it->second << endl;
				int ds = 0;
			}*/
		}
	
		ans += minget;

		//从已有的硬币里减去
		for (map<int, int>::iterator it = usedmm.begin(); it != usedmm.end(); it++) {
			int v = it->first;
			mm[v] -= minget * it->second;
		}
	}
}

int main()
{
	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int v, b; cin >> v >> b;
		if (v >= c) {
			ans += b;
		}
		else {
			mm[v] += b;
		}
	}

	solve();


	return 0;
}

 